1. Field of the Invention
The present invention relates generally to host adapters that interface two I/O buses, and more particularly, execution queues for host adapters.
2. Description of Related Art
Hardware control blocks, sometimes called sequencer control blocks or SCSI command blocks (SCBs), are typically used for transferring information between a software host adapter device driver in a host computer and a host adapter integrated circuit that controls operations of one or more peripheral devices. Methods for queuing SCBs are known to those of skill in the art.
For example, see copending and commonly assigned U.S. patent application Ser. No. 07/964,532 entitled xe2x80x9cIntelligent SCSI Bus Host Adapter Integrated Circuit,xe2x80x9d of Craig A. Stuber et al. filed on Oct. 16, 1992, which is incorporated wherein by reference in its entirety. See also, commonly assigned U.S. Pat. No. 5,625,800 entitled xe2x80x9cA Sequencer Control Block Array External To A Host Adapter Integrated Circuitxe2x80x9d of Michael D. Brayton et al. filed on Jun. 30, 1994; and also U.S. Pat. No. 5,564,023 entitled xe2x80x9cMethod for Accessing A Sequencer Control Block By A Host Adapter Integrated Circuitxe2x80x9d of B. Arlen Young issued on Oct. 8, 1996, each of which is incorporated herein by reference in its entirety.
A prior art method for queuing SCBs for a system 100, which included a processor 105 of a host system 106 and a host adapter device 120 with a sequencer 125, used a one-dimensional linked list SCB queue 160 within a SCB array 155 in random access memory 150. A device driver executing on microprocessor 105 managed host adapter 120 using SCBs, e.g., hardware control blocks, in SCB queue 160. Each SCB in SCB queue 160 had a next queue site field Q_NEXT, sometimes referred to as field Q_NEXT, that was used to store a SCB site pointer that addressed the next SCB storage site in SCB queue 160.
Queue 160 was delimited by head pointer 141 and tail pointer 142. Head pointer 141 was the number of the site in SCB array 155 storing the SCB to be executed next, and tail pointer 142 was the number of the site in SCB array 155 containing the last SCB transferred from host system 106. Next queue site field Q_NEXT in the site addressed by tail pointer 142 had an invalid value that was used to identify the SCB as the last in queue 160 in addition to tail pointer 142.
When queue 160 was empty, head pointer 141 was an invalid value. When a new SCB was transferred from host system 106 to SCB array 155, head pointer 141 and tail pointer 142 were changed to point to the storage site of the new SCB, i.e., were changed to valid values. Field Q_NEXT in the new SCB was set to an invalid value to indicate that the SCB was the last SCB in queue 160.
As each new SCB was transferred from host system 106 to SCB array 155, tail pointer 142 was used to identify the end of queue 160. Field Q_NEXT in the SCB pointed to by tail pointer 142 was changed to point to the newly transferred SCB, and then tail pointer 142 was changed to point to the storage site of the newly transferred SCB.
A valid head pointer 141 indicated that one or more commands were available for transfer to one or more SCSI targets. The next target selected was specified by information within the SCB addressed by head pointer 141. Host adapter 120 removed the SCB at the head of queue 160 for execution and selected the specified target. Head pointer 141 was changed to point to the next SCB in queue 160, i.e., the value in field Q_NEXT of the SCB removed for execution was copied to head pointer 141. When the selection process was complete, the command contained within the SCB was transferred to the target.
SCBs in array 160 were executed and targets were selected in the order that the SCBs were received from host system 106. This order is shown by the dashed line in FIG. 1. SCBs were not inserted or removed from the middle of queue 160.
Other methods are known for queuing SCSI command blocks for a SCSI target. See for example, U.S. Pat. Nos. 5,938,747 and 6,006,292, each of which is incorporated herein by reference. Independent of the method used to manage SCBs in a queue within the SCB array, SCBs are executed and targets are selected in the order that the SCBs were received from host system 106. SCBs are not inserted into or removed from the middle of the queue within the SCB array.
According to the principles of this invention, a command block execution queue stored in a memory includes a plurality of command blocks in a first linked list, sometimes called a common queue of command blocks. The first linked list is delimited by a head pointer and a tail pointer.
The command block execution queue further includes another plurality of command blocks in a second linked list. There is a specific relationship between the first and second linked lists. Specifically, one and only one of the another plurality of command blocks is included in the plurality of command blocks in the first linked list. The second linked list is delimited by only a tail pointer.
In another embodiment, the command block execution queue includes a common linked list of command blocks having a common head command block and a common tail command block. A head pointer addresses the common head command block, while a tail pointer addresses the common tail command block. The command block execution queue also includes a target linked list of command blocks having a target head command block and a target tail command block wherein only the target head command block is included in the common linked list of command blocks. Only a target tail pointer to the target tail command block delimits the target linked list.
In this embodiment, each command block includes a command for a target device, and the common linked list contains a maximum of one command block for a target. Also, in this embodiment, the target linked list contains only command blocks for a single target device.
The command block execution queue in a further embodiment includes another target linked list of command blocks having another target head command block and another target tail command block where one and only one of the another target head command blocks is included in the common linked list of command blocks, and where another target tail pointer addresses the another target tail command block. The target tail pointer and the another target tail pointer are included in a list of target tail pointers. Each command block includes a command for a target device having an identification number. The target linked list contains only command blocks for a single target device having a first identification number, and the another target linked list contains only command blocks for another single target device having a second identification number. The target tail pointer to the target tail command block is stored in the list of target tail pointers at a location determined by the first identification number. The another target tail pointer is stored in the list of target tail pointers at a location determined by the second identification number.
A method of managing a command block execution queue where each command block is associated with one of a plurality of target devices includes testing a predefined location in a list of target tail pointers to determine whether a target queue exists for a target device specified in a hardware command block. The method further includes appending the hardware command block to a tail of the target queue for the target device upon the testing indicating that the target queue exists, and appending the hardware command block to a tail of a common queue upon the testing indicating that the target queue does not exist.
In another embodiment, the method of managing a command block execution queue where each command block is associated with one of a plurality of target devices includes:
appending a new command block to a common tail command block of a common linked list of command blocks when the new command block is associated with a target device different from the target devices associated with the command blocks included in the common linked list of command blocks; and
appending the new command block to a target tail command block of a target linked list of command blocks when the new command block is associated with a target device which is a same target device as that associated with one of the command blocks included in the common linked list of command blocks wherein only one target command block of the target linked list is included in the common linked list of command blocks.